import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 10个工人 挖5座不同价值的金矿，每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿
 * 根据题目要求，选择使用0-1背包算法
 *
 * 假设金矿储量 1000kg，有5座金矿
 *
 * 金矿1，需要5个工人，500kg储量
 *
 * w[1] = 5 v[1] = 500kg
 *
 * 金矿2，需要3个工人，200kg储量
 *
 * w[2] = 3 v[2] = 200kg
 *
 * 金矿3，需要2个工人，100kg储量
 *
 * w[3] = 2 v[3] = 100kg
 *
 * 金矿4，需要3个工人，150kg储量
 *
 * w[4] = 3 v[4] = 150kg
 *
 * 金矿5，需要1个工人，50kg储量
 *
 * w[5] = 1  v[5] = 50kg
 */
public class GoldOre {

    /**
     * 最大价值
     * @param values 金矿储量
     * @param peoples 开挖所需人数
     * @param max 最多工人数
     * @return
     */
    public static Map<String,Object> maxValue(int[] values, int[] peoples, int max){
        Map<String,Object> rs = new HashMap<>();
        if (values == null || values.length == 0) return rs;
        if (peoples == null || peoples.length == 0) return rs;
        if (values.length != peoples.length || max <= 0) return rs;

        // dp 数组
        int[][] dp = new int[values.length + 1][max + 1];
        Set<Integer> goldNo = new HashSet<>();
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= max; j++) {
                // 选择的金矿所需人数大于当前工人数
                if (peoples[i-1] > j){
                    // 取值为上一轮的结果
                    dp[i][j] = dp[i-1][j];
                }else{
                    // 上一轮的价值
                    int preValue = dp[i-1][j];
                    // 当前这一轮
                    int currValue = values[i-1]+dp[i-1][j-peoples[i-1]];
                    dp[i][j] = Math.max(preValue,currValue);
                }
            }
        }
        int maxVal = dp[values.length][max];
        int j = max;
        rs.put("MaxValue",maxVal);
        for (int i = values.length; i > 0; i--) {
            if (dp[i][j] > dp[i-1][j]){
                goldNo.add(i);
                j = j - peoples[i-1];
            }
            if (j == 0) break;
        }
        rs.put("No.",goldNo);
        int p = 0;
        for (Integer s : goldNo){
            p += peoples[s-1];
        }
        rs.put("PeopleNum",p);

        return rs;
    }


    public static void main(String[] args) {
        int[] values = {500,200,100,150,50};
        int[] peoples = {5,3,2,3,1};
        int max = 10;
        Map<String, Object> map = maxValue(values, peoples, max);
        System.out.println("最多可挖取黄金:"+map.get("MaxValue"));
        System.out.println("最少需要的工人数:"+map.get("PeopleNum"));
        System.out.println("要挖的金矿编号为:"+map.get("No."));
    }
}